package com.leetcode.ask;

/**
 * @ClassName ReverseLinkedListHard
 * @Description 92. 反转链表 2
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * <p>
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author liyucheng
 * @Date 2020/10/12 9:04 下午
 * @Version 1.0
 **/
public class ReverseLinkedListHard {

    private static class ListNode {
        private int value;
        private ListNode next;

        public ListNode(int value) {
            this.value = value;
        }

        public ListNode() {
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

    public static ListNode reverseListHard(ListNode head, int m, int n) {
        //判断前两个节点是否为空
        if (head == null || head.next == null || m >= n) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        head = dummy;
        ListNode preM = head;
        for (int i = 1; i < m; i++) {
            preM = preM.next;
        }
        ListNode mNode = preM.next;
        ListNode pre = mNode;
        ListNode cur = pre.next;
        for (int i = m; i < n; i++){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        mNode.next = cur;
        preM.next = pre;
        return head.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode();
        listNode1.setValue(1);

        ListNode listNode2 = new ListNode();
        listNode2.setValue(2);
        listNode1.setNext(listNode2);


        ListNode listNode = reverseListHard(listNode1, 1, 2);
        while (listNode != null) {
            System.out.println(listNode.getValue());
            System.out.println(listNode.getNext());
            listNode = listNode.getNext();
        }

    }

}
